1. Field of the Disclosure
The present disclosure relates generally to network communication, and more specifically, to traffic engineering in networking systems.
2. Description of the Related Art
In a communication network, users establish connections between a source node and a destination node via a flow of data that is transferred through the network over one or more network paths. The data of one or more connections constitutes traffic over the network. A traffic demand in the network between the source node and the destination node is represented by a commodity. A network path for a commodity between the source and destination nodes is defined by a set of nodes (the source-destination node pair and any intermediate nodes) interconnected by a set of links coupled to the nodes carrying the data flow of the commodity. Each node and each link has a capacity corresponding to the traffic it may carry.
The allocation of global shared resources to different users of a network is a fundamental problem in distributed computing and networking. A well accepted principle is that network resources, such as network capacity, belong to all users and thus should be shared among the users in a fair and non-discriminatory way. However, it is important to optimize fairness with throughput, to ensure that resources of the network are utilized as much as possible.
In one known fair allocation strategy, known as max-min fairness, resources are allocated in order of increasing demands—broadly speaking, low-traffic commodities are given all the capacity they want, while high-traffic commodities evenly split the remaining capacity of the network. More specifically, the max-min fairness strategy first maximizes the smallest allocation among all commodities; it then maximizes the second smallest allocation subject to the first maximized smallest allocation, and so on. An allocation is max-min fair if in order to increase the flow allocated to a commodity, a flow allocated to a commodity with an equal or less flow would have to be decreased.
In the restricted case where each commodity has a single path connecting its source to its destination, the min-max fairness allocation may be determined using the known WaterFill algorithm, which progressively fills the demands of commodities at the same rate until capacities of the network links are saturated. In the more general and realistic case where each commodity can be sent along multiple paths connecting its source to its destination, the standard approach for finding the max-min fairness allocation requires an iterative solution of multiple linear programs. Such an approach has several limitations. First, it scales badly with the size of the network, the number of demands, and the number of paths. Second, it provides the network operator limited control and understanding of the inner working of the allocation scheme. Third, it is inherently centralized and may not be implemented in a distributed manner. Fourth, it may be unstable because a minor change in the capacity of the network or traffic demands may have a significant effect on the determined allocation.